package main.Q1001_1100;

import java.util.*;

public class Q1021_1030 {
    public static void main(String[] args) {
        System.out.println("Question1021：删除最外层的括号");
        System.out.println("Question1022：");
        System.out.println("Question1023：");
        System.out.println("Question1024：");
        System.out.println("Question1025：除数博弈");
        System.out.println("Question1026：节点与其祖先之间的最大差值");
        System.out.println("Question1027：");
        System.out.println("Question1028：从先序遍历还原二叉树");
        System.out.println(new Question1028().recoverFromPreorder("1-2--3---4-5--6---7"));
        System.out.println("Question1029：两地调度");
        System.out.println("Question1030：距离顺序排列矩阵单元格");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Question1021 {
    public String removeOuterParentheses(String s) {
        StringBuffer res = new StringBuffer();
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')') {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                res.append(c);
            }
            if (c == '(') {
                stack.push(c);
            }
        }
        return res.toString();
    }
}

class Question1025 {
    public boolean divisorGame(int n) {
        return n % 2 == 0;
    }
}

class Question1026 {
    int max = 0;

    public void process(TreeNode root, int maxVal, int minVal) {
        if (root == null) return;
        max = Math.max(max, Math.max(Math.abs(maxVal - root.val), Math.abs(minVal - root.val)));
        maxVal = Math.max(maxVal, root.val);
        minVal = Math.min(minVal, root.val);
        process(root.left, maxVal, minVal);
        process(root.right, maxVal, minVal);
    }

    public int maxAncestorDiff(TreeNode root) {
        process(root, root.val, root.val);
        return max;
    }
}

class Question1028 {
    public TreeNode recoverFromPreorder(String traversal) {
        Deque<TreeNode> result = new LinkedList<TreeNode>();
        int pos = 0;
        while (pos < traversal.length()) {
            int level = 0;
            while (traversal.charAt(pos) == '-') {
                ++level;
                ++pos;
            }
            int value = 0;
            while (pos < traversal.length() && Character.isDigit(traversal.charAt(pos))) {
                value = value * 10 + (traversal.charAt(pos) - '0');
                ++pos;
            }
            TreeNode node = new TreeNode(value);
            if (level == result.size()) {
                if (!result.isEmpty()) {
                    result.peek().left = node;
                }
            } else {
                while (level != result.size()) {
                    result.pop();
                }
                result.peek().right = node;
            }
            result.push(node);
        }
        while (result.size() > 1) {
            result.pop();
        }
        return result.peek();
    }
}

class Question1029 {
    public int twoCitySchedCost(int[][] costs) {
        int n = costs.length / 2, min = 0;
        Arrays.sort(costs, Comparator.comparingInt(a -> (a[0] - a[1])));
        for (int i = n - 1; i >= 0; i--) {
            min += costs[i][0] + costs[i + n][1];
        }
        return min;
    }
}

class Question1030 {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int[][] result = new int[rows * cols][];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                result[i * cols + j] = new int[]{i, j};
            }
        }
        Arrays.sort(result, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return (Math.abs(a[0] - rCenter) + Math.abs(a[1] - cCenter)) - (Math.abs(b[0] - rCenter) + Math.abs(b[1] - cCenter));
            }
        });
        return result;
    }
}